package leetcode_周赛._2023._08;

import java.util.*;

/**
 * 第 357 场周赛
 * <p>AC_2</p>
 *
 * @author yezh
 * @date 2023/8/14 8:56
 */
public class _06 {

    /**
     * 2810.故障键盘 <br />
     * 算法: 模拟
     */
    public static String finalString(String s) {
        Deque<Character> queue = new ArrayDeque<>();
        boolean flag = true;
        for (char c : s.toCharArray()) {
            if (c == 'i') flag = !flag;
            else if (flag) queue.addLast(c);
            else queue.addFirst(c);
        }
        StringBuilder ans = new StringBuilder();
        while (!queue.isEmpty()) ans.append(queue.pollFirst());
        return flag ? ans.toString() : ans.reverse().toString();
    }

    /**
     * 2812.找出最安全路径 <br />
     * 算法: 多源 BFS + 并查集
     */
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        List<int[]> q = new ArrayList<>();
        int[][] dis = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) q.add(new int[]{i, j});
                else dis[i][j] = -1;
            }
        List<List<int[]>> g = new ArrayList<>();
        g.add(q);
        while (!q.isEmpty()) {
            List<int[]> tmp = q;
            q = new ArrayList<>();
            for (int[] p : tmp) {
                int i = p[0], j = p[1];
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (0 <= x && x < n && 0 <= y && y < n && dis[x][y] == -1) {
                        dis[x][y] = g.size();
                        q.add(new int[]{x, y});
                    }
                }
            }
            g.add(q);
        }
        fa = new int[n * n];
        for (int ans = g.size() - 2; ans > 0; --ans) {
            for (int[] p : g.get(ans)) {
                int i = p[0], j = p[1];
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (0 <= x && x < n && 0 <= y && y < n && dis[x][y] >= dis[i][j])
                        fa[find(x * n + y)] = fa[find(i * n + j)];
                }
            }
            if (find(0) == find(n * n - 1)) return ans;
        }
        return 0;
    }

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[] fa;

    int find(int x) {
        if (fa[x] != x) fa[x] = find(x);
        return fa[x];
    }

}
